package leetcode

import tree.TreeNode
import java.util.*
import kotlin.collections.ArrayList

//https://leetcode.com/problems/binary-tree-inorder-traversal/

class TreeNodeImpl(var `val`: Int, var left: TreeNodeImpl?, var right: TreeNodeImpl?) {
//    var left: TreeNode? = null
//    var right: TreeNode? = null
}


val treeRoot1 = TreeNodeImpl(
        1,
        TreeNodeImpl(
                2,
                TreeNodeImpl(
                        4,
                        null,
                        null
                ),
                TreeNodeImpl(5,
                        TreeNodeImpl(7,
                                null,
                                null),
                        TreeNodeImpl(8,
                                null,
                                null))
        ),
        TreeNodeImpl(3,
                null,
                TreeNodeImpl(6,
                        null,
                        null))
)

fun main(args: Array<String>) {
    val t = TreeNodeImpl(
            2,
            TreeNodeImpl(3,
                    TreeNodeImpl(1,
                            null,
                            null),
                    null),
            null)
    println(SolutionTreeNode().inorderTraversal(treeRoot1))
}

class SolutionTreeNode {


    fun inorderTraversal(root: TreeNodeImpl?): List<Int> {
        val stack = arrayListOf<TreeNodeImpl?>()
        val result = arrayListOf<Int>()
        if (root == null)
            return result
        stack.add(root)
        while (stack.isNotEmpty()) {
            val node = stack.removeAt(stack.lastIndex)
            if (node != null && (node.left != null || node.right != null)) {
                stack.add(node.right!!)
                stack.add(node)
                stack.add(node.left!!)
            } else {
                var parent: TreeNodeImpl? = null
                if (stack.isNotEmpty()) parent = stack.removeAt(stack.lastIndex)
                if (node == null) {
                    if (parent != null)
                        result.add(parent.`val`)
                } else {
                    result.add(node.`val`)
                    if (parent != null)
                        result.add(parent.`val`)
                }
            }
        }
        return result
    }
}